package Tree;

import java.util.*;
import java.util.stream.Collector;
import java.util.stream.Collectors;

/**
 * 迭代
 * 中序遍历
 */
public class InOrderTraversalIteration {
    public static List<Integer> inorder(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while(!stack.isEmpty() || root != null ){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode r_left = new TreeNode(2);
        TreeNode right = new TreeNode(3,r_left,null);
        TreeNode root = new TreeNode(1,null,right);
        List<Integer> res = inorder(root);
       res.forEach(x->{
           System.out.println(x);
       });
    }
}
